package leetcode.year2021.month10;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 102. 二叉树的层序遍历
 * 思路，使用队列或者栈存储每一层的值，然后调用下一次的时候，根据队列求得所有子节点，然后清空队列中上一次的数据
 */
public class _24_03LevelOrder102 {

  public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    Deque<TreeNode> queue = new LinkedList<>();
    if (root == null){
      return ans;
    }
    queue.add(root);
    while (!queue.isEmpty()){
      int length = queue.size();
      ans.add(new ArrayList<>(queue.stream().map(node -> node.val).collect(Collectors.toList())));
      for (int i = 0; i < length; i++) {
        TreeNode pop = queue.pop();
        if (pop.left != null){
          queue.add(pop.left);
        }
        if (pop.right != null){
          queue.add(pop.right);
        }
      }
    }
    return ans;
  }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }

      public int getVal() {
        return val;
      }
    }

  /**
   * 102. 二叉树的层序遍历
   * 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
   *
   *
   *
   * 示例：
   * 二叉树：[3,9,20,null,null,15,7],
   *
   *     3
   *    / \
   *   9  20
   *     /  \
   *    15   7
   * 返回其层序遍历结果：
   *
   * [
   *   [3],
   *   [9,20],
   *   [15,7]
   * ]
   */
}
